One class of error correcting codes is that of the so called turbo codes. A turbo code is decoded by a turbo decoder. Turbo decoders are characterized by comprising at least two elementary decoders who cooperate to produce decoded data.
Turbo codes are employed, e.g., in communications protocols, such as used for mobile telephony. For example, a sender, encodes original data using a turbo encoder for use during transmission, a receiver decodes received data using a turbo decoder. During transmission errors may occur. The use of a turbo encoder and turbo decoder allows the correction of some errors. One protocol in which turbo codes are used is the High-Speed Downlink Packet Access (HSDPA) protocol.
Each elementary decoder takes as input the received data and the results of a previous elementary decoding operation, done by another elementary decoder. During execution the elementary decoders work on so-called soft data. Soft data gives probabilistic information on the data that was originally sent. In addition the soft data may comprise bit reliabilities. The elementary decoders need to be able to use soft data, for example, SISO decoders (Soft Input Soft Output). The soft data can be transformed into hard data. Hard data consists of a specific guess of what the data, that was originally sent by the sender, was.
The structure and operation of turbo decoders is well known to a person skilled in the art. Turbo decoders are, for example, described in S. A. Barbulescu and S. S. Pietrobon, “Turbo codes: A tutorial on a new class of powerful error correcting coding schemes, Part 1: Code structures and interleaver design”, J. Elec. and Electron. Eng., Australia, vol. 19, pp. 129-142, September 1999. and S. A. Barbulescu and S. S. Pietrobon, “Turbo codes: A tutorial on a new class of powerful error correcting coding schemes, Part 2: Decoder design and performance,” J. Elec. and Electron. Eng., Australia, vol. 19, pp. 143-152, September 1999.
A turbo decoder comprises an iterative algorithm comprising a number of iterations. Each iteration comprises the execution of each of the elementary decoders. The classical implementation of this iterative algorithm performs a constant number of iterations independent of the channel condition, such as the signal to noise ratio. The ability to dynamically determine the number of iterations is called “Early stopping”. The current state of the art comprises several techniques for early stopping.
One such approach for early stopping is described in U.S. Pat. No. 7,093,180 B2. In U.S. Pat. No. 7,093,180 B2 the turbo decoding is organized in a series of iterations. Each iteration consists of decodings by all the component decoders. At the end of each full iteration it is determined if convergence or divergence has occurred. If so, the iteration is stopped.
A comprehensive overview of the state of the art of early stopping rules is provided by “Stopping Rules for Turbo Decoders”; TMO progress report 42-142; Aug. 15, 2000; A. Matache, S. Dolinar and F. Pollara. Herein a turbo decoder with two elementary decoders is used. The report proposes a first method for early stopping. The first method stops elementary decoding as soon as the outputs of the two elementary decoders are equal. This first method is applied after each elementary decoding. Also a second self-contained method for early stopping is proposed. The second method stops elementary decoding as soon as the second elementary decoder has converged; this rule is only applied after an elementary decoding done by the second elementary decoder.
It is a problem of the prior art that turbo encoders need many elementary decodings.